﻿using System.Linq;

namespace NahidaProject4CSharp.Generic
{
	public class SortModule
	{
		public static void BubbleSort(int[] arr)
		{
			int n = arr.Length;
			for (int i = 0; i < n - 1; i++)
			{
				bool swapped = false;
				for (int j = 0; j < n - 1 - i; j++)
				{
					if (arr[j] > arr[j + 1])
					{
						Swap(arr, j, j + 1);
						swapped = true;
					}
				}
				// 如果没有发生交换，说明已经有序
				if (!swapped) break;
			}
		}

		public static void SelectionSort(int[] arr)
		{
			int n = arr.Length;
			for (int i = 0; i < n - 1; i++)
			{
				int minIndex = i;
				// 找到最小元素的索引
				for (int j = i + 1; j < n; j++)
				{
					if (arr[j] < arr[minIndex])
						minIndex = j;
				}
				// 交换最小元素到当前位置
				if (minIndex != i)
					Swap(arr, i, minIndex);
			}
		}

		public static void InsertionSort(int[] arr)
		{
			int n = arr.Length;
			for (int i = 1; i < n; i++)
			{
				int key = arr[i];
				int j = i - 1;
				// 将大于key的元素向后移动
				while (j >= 0 && arr[j] > key)
				{
					arr[j + 1] = arr[j];
					j--;
				}
				arr[j + 1] = key;
			}
		}
		public static void QuickSort(int[] arr, int low, int high)
		{
			if (low < high)
			{
				int pivotIndex = Partition(arr, low, high);
				QuickSort(arr, low, pivotIndex - 1);
				QuickSort(arr, pivotIndex + 1, high);
			}
		}

		private static int Partition(int[] arr, int low, int high)
		{
			int pivot = arr[high]; // 选择最后一个元素作为基准
			int i = low - 1;

			for (int j = low; j < high; j++)
			{
				if (arr[j] <= pivot)
				{
					i++;
					Swap(arr, i, j);
				}
			}
			Swap(arr, i + 1, high);
			return i + 1;
		}
		public static void MergeSort(int[] arr, int left, int right)
		{
			if (left < right)
			{
				int mid = left + (right - left) / 2;
				MergeSort(arr, left, mid);
				MergeSort(arr, mid + 1, right);
				Merge(arr, left, mid, right);
			}
		}

		private static void Merge(int[] arr, int left, int mid, int right)
		{
			int n1 = mid - left + 1;
			int n2 = right - mid;

			// 创建临时数组
			int[] leftArr = new int[n1];
			int[] rightArr = new int[n2];

			// 复制数据到临时数组
			for (int i = 0; i < n1; i++)
				leftArr[i] = arr[left + i];
			for (int i = 0; i < n2; i++)
				rightArr[i] = arr[mid + 1 + i];

			// 合并临时数组
			int i1 = 0, i2 = 0, k = left;
			while (i1 < n1 && i2 < n2)
			{
				if (leftArr[i1] <= rightArr[i2])
				{
					arr[k] = leftArr[i1];
					i1++;
				}
				else
				{
					arr[k] = rightArr[i2];
					i2++;
				}
				k++;
			}

			// 复制剩余元素
			while (i1 < n1)
			{
				arr[k] = leftArr[i1];
				i1++;
				k++;
			}
			while (i2 < n2)
			{
				arr[k] = rightArr[i2];
				i2++;
				k++;
			}
		}
		public static void HeapSort(int[] arr)
		{
			int n = arr.Length;

			// 构建最大堆
			for (int i = n / 2 - 1; i >= 0; i--)
				Heapify(arr, n, i);

			// 逐个提取元素
			for (int i = n - 1; i > 0; i--)
			{
				Swap(arr, 0, i); // 将当前最大元素移到末尾
				Heapify(arr, i, 0); // 重新调整堆
			}
		}

		private static void Heapify(int[] arr, int n, int i)
		{
			int largest = i;
			int left = 2 * i + 1;
			int right = 2 * i + 2;

			if (left < n && arr[left] > arr[largest])
				largest = left;

			if (right < n && arr[right] > arr[largest])
				largest = right;

			if (largest != i)
			{
				Swap(arr, i, largest);
				Heapify(arr, n, largest);
			}
		}
		public static void ShellSort(int[] arr)
		{
			int n = arr.Length;
			for (int gap = n / 2; gap > 0; gap /= 2)
			{
				for (int i = gap; i < n; i++)
				{
					int temp = arr[i];
					int j;
					for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
					{
						arr[j] = arr[j - gap];
					}
					arr[j] = temp;
				}
			}
		}
		public static void CountingSort(int[] arr)
		{
			if (arr.Length == 0) return;

			int max = arr.Max();
			int min = arr.Min();
			int range = max - min + 1;

			int[] count = new int[range];
			int[] output = new int[arr.Length];

			// 计算每个元素出现的次数
			for (int i = 0; i < arr.Length; i++)
				count[arr[i] - min]++;

			// 计算累积计数
			for (int i = 1; i < count.Length; i++)
				count[i] += count[i - 1];

			// 构建输出数组
			for (int i = arr.Length - 1; i >= 0; i--)
			{
				output[count[arr[i] - min] - 1] = arr[i];
				count[arr[i] - min]--;
			}

			// 复制回原数组
			for (int i = 0; i < arr.Length; i++)
				arr[i] = output[i];
		}

		private static void Swap(int[] arr, int i, int j)
		{
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
}
